//date : 2019-04-15 22:15:44
//source : https://leetcode.com/problems/two-sum/

// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
// You may assume that each input would have exactly one solution, and you may not use the same element twice.
// Example:
// Given nums = [2, 7, 11, 15], target = 9,
// Because nums[0] + nums[1] = 2 + 7 = 9,
// return [0, 1].

// time complexity: o(n) ;
// space complexity: 0(n);

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution{
public:
    vector<int> twosum(vector<int>& nums,int target){
        unordered_map<int,int> mapNums;
        for(int i=0;i<nums.size();i++){
            mapNums.insert(make_pair(nums[i],i));
        }
        unordered_map<int,int>::iterator it;
        for(int i=0;i<nums.size();i++){
            if((it = mapNums.find(target-nums[i])) != mapNums.end() && it != mapNums.find(nums[i])){
                vector<int> result = {i,it->second};
                return result;
            }
        }
        throw "no such two sum";
    }
};

int main(){
    vector<int> exNums = {2,4,11,8};
    int exTarget = 9;
    Solution ex;
    try{
        vector<int> exResult = ex.twosum(exNums,exTarget);
        vector<int>::iterator it;
        for(it=exResult.begin();it!=exResult.end();it++){
            cout << *it << " ";
        }
    }catch(const char* msg){
        cerr << msg << endl;
    }
}
